package interviewclassic;

import java.util.HashSet;
import java.util.Set;

/**
 * @author ZhanBo
 * @date 2020/7/31
 */
public class Solution0201 {

    public static void main(String[] args) {

    }


    /**
     * 面试题 02.01. 移除重复节点
     * 编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
     *
     *  输入：[1, 2, 3, 3, 2, 1]
     *  输出：[1, 2, 3]
     * @param head
     * @return
     */
    public ListNode removeDuplicateNodes(ListNode head) {
        if (head == null || head.next ==null ){
            return head;
        }
        ListNode temp = head;
        Set<Integer> set = new HashSet<>();
        set.add(head.val);
        while (temp.next!=null){
            ListNode cur = temp.next;
            if (!set.contains(cur.val)){
                set.add(cur.val);
                temp = temp.next;
            }else {
                temp.next = temp.next.next;
            }
        }
        temp.next= null;
        return head;
    }

    public ListNode removeDuplicateNodes2(ListNode head) {
        if (head == null) {
            return head;
        }
        Set<Integer> occurred = new HashSet<Integer>();
        occurred.add(head.val);
        ListNode pos = head;
        // 枚举前驱节点
        while (pos.next != null) {
            // 当前待删除节点
            ListNode cur = pos.next;
            if (occurred.add(cur.val)) {
                pos = pos.next;
            } else {
                pos.next = pos.next.next;
            }
        }
        pos.next = null;
        return head;
    }
}
